package edu.unice.simul.util.graphs;

import java.util.ArrayList;
import java.util.List;

import edu.unice.simul.conf.GeneralSettings;

/**
 * Cette classe représente un graphe.
 * 
 * @author Romain Ciaccafava
 * 
 */
public class Graphe {
	/**
	 * Sommet de départ du graphe.
	 */
	private Sommet sommetDepart;
	private List<Sommet> sommets = new ArrayList<Sommet>();
	private List<Integer> sommetsVisites = new ArrayList<Integer>();

	/**
	 * Création du graphe
	 * 
	 * @param sommetDepart
	 *          sommet de départ du graphe
	 */
	public Graphe(Sommet sommetDepart) {
		this.sommetDepart = sommetDepart;
		if (GeneralSettings.DEBUG)
			System.err.println("Sommet de départ : "
					+ sommetDepart.getBlock().getPos());
		this.visiterGraphe();
	}

	/**
	 * Retourne le sommet de départ
	 */
	public Sommet getSommetDepart() {
		return this.sommetDepart;
	}

	/**
	 * Retourne les sommets du graphes
	 */
	public List<Sommet> getSommets() {
		return this.sommets;
	}

	/**
	 * Visite le graphe
	 */
	private void visiterGraphe() {
		sommets.add(this.sommetDepart);
		marquerCommeVisite(sommetDepart);
		for (Arc e : this.sommetDepart.getArcsSortants()) {
			if (!estVisite(e.getSommetDestination())) {
				premiereRecherche(e.getSommetDestination());
			}
		}
	}

	/**
	 * Première recherche d'un sommet
	 */
	private void premiereRecherche(Sommet n) {
		marquerCommeVisite(n);
		this.sommets.add(n);
		for (Arc e : n.getArcsSortants()) {
			if (!estVisite(e.getSommetDestination())) {
				premiereRecherche(e.getSommetDestination());
			}
		}
	}

	/**
	 * Renseigne si un sommet a déjà été visité
	 */
	private boolean estVisite(Sommet n) {
		return sommetsVisites.contains(n.getID());
	}

	/**
	 * Marque comme visité un sommet
	 */
	private void marquerCommeVisite(Sommet n) {
		this.sommetsVisites.add(n.getID());
	}

}
